package com.yubest;

import java.util.*;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * 有效括号组合需满足：左括号必须以正确的顺序闭合。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 *
 * 提示：
 *
 * 1 <= n <= 8
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/generate-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/1 14:35
 */
public class P0022 {

    public static void main(String[] args) {
        System.out.println(new Solution22().generateParenthesis(3));

        System.out.println(new Solution22().generateParenthesis(1));
    }
}

class Solution22 {

    private Map<Integer, List<String>> map = new HashMap<>();

    /**
     * 思路：递归
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if (n == 1) {
            result.add("()");
            return result;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        }
        List<String> pre = generateParenthesis(n - 1);
        Set<String> set = new HashSet<>();
        StringBuilder buf;
        for (String s : pre) {
            for (int i = 0; i < s.length(); i++) {
                buf = new StringBuilder();
                if (i == 0) {
                    buf.append("()").append(s);
                } else {
                    buf.append(s.substring(0, i)).append("()").append(s.substring(i));
                }
                set.add(buf.toString());
            }
        }
        result.addAll(set);
        map.put(n, result);
        return result;
    }
}
